package com.fps.webshop.question.question0001_0099;

/**
 * 21. 合并两个有序链表
 * 
 * 将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 
 * 
 * 示例 1：
 * Question021_01.jpg
 * 输入：l1 = [1,2,4], l2 = [1,3,4]
 * 输出：[1,1,2,3,4,4]
 * 
 * 示例 2：
 * 输入：l1 = [], l2 = []
 * 输出：[]
 * 
 * 示例 3：
 * 输入：l1 = [], l2 = [0]
 * 输出：[0]
 * 
 * 提示：
 * 		两个链表的节点数目范围是 [0, 50]
 * 		-100 <= Node.val <= 100
 * 		l1 和 l2 均按 非递减顺序 排列
 */
public class Question021 {

	public class ListNode {
		int val;
		ListNode next;
		ListNode() {
		}
		ListNode(int val) {
			this.val = val;
		}
		ListNode(int val, ListNode next) {
			this.val = val;
			this.next = next;
		}
	}
	/**
	 * 第一次提交，链表的简单遍历
	 * 
	 * 提交结果	执行用时	内存消耗	语言		提交时间				备注 
	 * 通过 		0 ms	37.7 MB	Java	2021/08/16 18:03
	 * 
	 * 执行用时：0 ms, 在所有 Java 提交中击败了100.00%的用户
	 * 内存消耗：37.7 MB, 在所有 Java 提交中击败了74.01%的用户
	 */
	public static ListNode mergeTwoLists1(ListNode l1, ListNode l2) {
		if(l1==null) {
			return l2;
		}
		if(l2==null) {
			return l1;
		}
		ListNode newList = null;
		ListNode newHead = null;
		while(l1!=null&&l2!=null) {
			if(l1.val<l2.val) {
				if(newList==null) {
					newList = l1;
					newHead = l1;
				}else {
					newList.next = l1;
					newList = newList.next;
				}
				l1 = l1.next;
			}else {
				if(newList==null) {
					newList = l2;
					newHead = l2;
				}else {
					newList.next = l2;
					newList = newList.next;
				}
				l2 = l2.next;
			}
		}
		if(newList!=null&&l1!=null) {
			newList.next = l1;
		}
		if(newList!=null&&l2!=null) {
			newList.next = l2;
		}
		return newHead;
    }
	
	public static void main(String[] args) {
		ListNode l1 = null;
		ListNode l2 = null;
		ListNode l = mergeTwoLists1(l1,l2);
		while(l.next!=null) {
			System.out.print(l.val+" ");
		}
	}
}
